Skip to main content

06 随机近似与随机梯度下降

06 随机近似与随机梯度下降​

平均数计算​

简单地计算Σi=1Nxi/N\Sigma_{i=1}^N x_i / N可以得到精确的平均数；但是这种方式只有样本全部到达才能进行。可以采用迭代式的方式计算平均数。

wk−1=1k−1Σi=1k−1xiwk=wk−1−1k(wk−1−xk)\begin{gather*} w_{k - 1} = \frac{1}{k - 1}\Sigma_{i=1}^{k-1}x_i \\ w_k = w_{k - 1} - \frac{1}{k}(w_{k-1} - x_k) \end{gather*}

事实上，这种算法就是一种随机近似算法，同时也是随机梯度下降算法。

随机近似与Robbins-Monro 算法​

随机近似（SA）指一系列随机迭代式算法，用于解方程或者优化问题。这种算法不需要知道实际的方程表达式。

RM算法是一种迭代式算法，用于解决g(w)=0g(w)=0问题。这种算法通过数据求得最优解w∗w^*。

wk+1=wk−akg~(wk,ηk)w_{k + 1} = w_k - a_k \widetilde{g}(w_k, \eta_k)

上式中，wkw_k为第kk次迭代得到的结果，g~(wk,ηk)\widetilde{g}(w_k, \eta_k)是输入wkw_k后得到的带有噪声ηk\eta_k的观测值（直接输入可能得到的不是完美观测值），aka_k是一个正系数（可理解为步长）。

RM算法需要三个条件（证明略）：

  • 对于所有ww，0<c1≤∇wg(w)≤c20 < c_1 \le \nabla_wg(w) \le c_2，函数单调递增
  • Σi=1Nak=∞\Sigma_{i=1}^Na_k = \infty，Σi=1Nak2<∞\Sigma_{i=1}^Na_k^2 < \infty
  • E[ηk∣Hk]=0E[\eta_k|\Eta_k]=0，E[ηk2∣Hk]<∞E[\eta_k^2|\Eta_k] < \infty

SGD​

SGD是一种特殊的RM算法。它解决的问题是minJ(w)=E[f(w,X)]minJ(w)=E[f(w,X)]，其中XX是随机变量，ww是待优化参数，EE是相对于XX的期望。

GD（梯度下降）算法为

wk+1=wk−αk∇wE[f(wk,X)]=wk−αkE[∇wf(wk,X)]w_{k + 1} = w_k - \alpha_k \nabla_wE[f(w_k, X)] = w_k - \alpha_kE[\nabla_wf(w_k, X)]

这里需要求梯度的期望。如果没有模型，可以通过数据的方式来求，也就是BGD（批量梯度下降）。

E[∇wf(wk,X)]≈1nΣi=1n∇wf(wk,xi)E[\nabla_wf(w_k, X)] \approx \dfrac{1}{n}\Sigma_{i=1}^n\nabla_wf(w_k, x_i)

对于这种方案，每次更新都需要进行一次估计，也就是说每次更新都需要多次采样。将其进一步简化，就得到了SGD（随机梯度下降）。

wk+1=wk−αk∇wf(wk,xk)w_{k + 1} = w_k - \alpha_k \nabla_wf(w_k, x_k)

SGD将XX的期望改为了XX的一个采样xkx_k。

可以通过证明SGD是一种特殊RM算法来证明它的有效性（指最终可以收敛到w∗w^*）。

由于SGD有一定随机性，所以不会向梯队下降那样每次都走向最优的方向；但是可以证明，在ww距w∗w^*比较远时，SGD的误差较小，更类似GD。

在另一种情况中，可能要解决这样一个问题：

minJ(w)=1nΣi=1nf(w,xi)minJ(w)=\frac{1}{n}\Sigma_{i=1}^nf(w, x_i)

此时没有随机变量，但是有一组{xi,f(xi)}\{x_i, f(x_i)\}。这种情况下，可以假设存在一个随机变量XX，它取每个xix_i的概率是1/n1/n；这种情况下，就将原问题转换为了SDG问题。这种情况下，可以随机取f(xi)f(x_i)代替Σi=1nf(w,xi)/n\Sigma_{i=1}^nf(w, x_i) / n，通过模拟随机变量的行为解决问题。

MBGD​

MBGD是介于BGD和SGD之间的算法。BGD每次要计算所有样本的均值，SGD只使用一个样本的值；而MBGD会随机选取一定量的样本求均值，用来替代期望。

相比SGD，MBGD可以更准确；相比BGD，MBGD更灵活和高效。注意，即使MBGD选取的样本量和总样本量相等，MBGD也不等于BGD，因为MBGD通过随机抽样的方式获取样本，一个样本可能被多次使用。

显然，BGD具有最快的收敛速度（不考虑均值计算），MBGD次之，SGD最慢。